package 第3节函数;

public class RecursionDemo02 {
    public static void main(String[] args) {
        System.out.println(f(5));
        System.out.println(f(10));
        System.out.println(f(50)); //O(2^n)
    }
    /*
    1 1 2 3 5 8 13 21 34 55 89 ......
    f(x) = f(x - 1) + f(x - 2)
                            f(5) = f(4) + f(3)
            f(4) = f(3) + f(2)              f(3) = f(2) + f(1)
    f(3) = f(2) + f(1)                  f(2) = 1          f(1) = 1
f(2) = 1            f(1) = 1
        1, x = 1 , x = 2
f(x)
        f(x - 1) + f(x - 2) , x > 2
    */
    public static int f(int x) {
        if (x == 1 || x == 2) {
            return 1;
        }
        return f(x - 1 ) + f(x - 2);
    }
}
